import java.util.*;

public class BinaryTree {
    static class Node{
        private int val;
        private Node left;
        private Node right;
        public Node(int val){
            this.val = val;
        }
    }
    static class PositionNode{
        private Node node;
        private int dep;
        private int pos;

        public PositionNode(Node node, int dep, int pos) {
            this.node = node;
            this.dep = dep;
            this.pos = pos;
        }
    }
    private Node root;
    private void create(){
        Node A = new Node(1);
        Node B = new Node(2);
        Node C = new Node(3);
        Node D = new Node(4);
        Node E = new Node(5);
        Node F = new Node(6);
        A.left = B;
        A.right = C;
        C.right = E;
        root = A;
    }
    private void recursion(Node root){
        if (root == null) return;

        recursion(root.left);
        recursion(root.right);
        System.out.print(root.val + " ");
    }
    private void frontErgodic(){
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node tmp = stack.pop();
            System.out.print(tmp.val + " ");
            if (tmp.right != null){
                stack.push(tmp.right);
            }
            if (tmp.left != null){
                stack.push(tmp.left);
            }
        }
    }
    private void centerErgodic(){
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node tmp = root;
        while (tmp != null || !stack.isEmpty()){
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.left;
            }
            Node cur = stack.pop();
            System.out.print(cur.val + " ");
            tmp = cur.right;
        }
    }
    private void backErgodic(){
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node tmp = root;
        Node prev = null;
        while (tmp != null || !stack.isEmpty()){
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.left;
            }
            tmp = stack.pop();
            if (tmp.right == null || tmp.right == prev){
                System.out.print(tmp.val + " ");
                prev = tmp;
                //将tmp置为空,会跳过左树的重复判断,然后栈顶重新弹出元素
                tmp = null;
            }else {
                stack.push(tmp);
                tmp = tmp.right;
            }
        }
    }
    private Node mergeTrees(Node root1, Node root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        Node root = new Node(root1.val+root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }
    private int widthOfBinaryTree(Node root) {
        if (root == null) return 0;
        Queue<PositionNode> queue = new LinkedList<>();
        queue.offer(new PositionNode(root,0,0));
        int ans = 0,dep = 0,left = 0;
        while (!queue.isEmpty()){
            PositionNode positionNode = queue.poll();
            if (positionNode.node != null){
                queue.offer(new PositionNode(positionNode.node.left,positionNode.dep+1,positionNode.pos*2+1));
                queue.offer(new PositionNode(positionNode.node.right,positionNode.dep+1,positionNode.pos*2+2));
                if (positionNode.dep != dep){
                    left = positionNode.pos;
                    dep = positionNode.dep;
                }
                ans = Math.max(ans,positionNode.pos-left+1);
            }
        }
        return ans;
    }
    private int heightBinaryTree(Node root){
        if (root == null) return 0;
        int left = heightBinaryTree(root.left);
        int right = heightBinaryTree(root.right);
        return Math.max(left,right) + 1;
    }
    private List<Integer> tierErgodic(){
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            list.add(cur.val);
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
        return list;
    }
    private boolean isCompleteTree(Node root) {
        if (root == null) return true;
        Queue<Node> queue = new LinkedList<>();
        Node cur = root;
        while (cur != null){
            queue.offer(cur.left);
            queue.offer(cur.right);
            cur = queue.poll();
        }
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            if (queue.poll() != null){
                return false;
            }
        }
        return true;
    }
    private boolean binaryTreeIsSame(Node root1,Node root2){
        if (root1 == null && root2 == null) {
            return true;
        } else if (root1 == null || root2 == null) {
            return false;
        } else if (root1.val != root2.val) {
            return false;
        } else {
            return binaryTreeIsSame(root1.left, root2.left) && binaryTreeIsSame(root1.right, root2.right);
        }
    }
    private boolean binaryTreeIsSamePlus(Node root1,Node root2){
        if (root1 == null && root2 == null) {
            return true;
        } else if (root2 == null) {
            return true;
        }else if (root1 == null){
            return false;
        } else if (root1.val != root2.val) {
            return false;
        }else {
          return  binaryTreeIsSamePlus(root1.left,root2.left) && binaryTreeIsSamePlus(root1.right,root2.right);
        }
    }
    private Queue<Node> queueErgodic(Queue<Node> queue,Node root){
        if (root == null) return null;
        queue.offer(root);
        queueErgodic(queue,root.left);
        queueErgodic(queue,root.right);
        return queue;
    }
    private boolean isContain(Node root1,Node root2){
        if (root1 == null && root2 == null) return true;
        if (root1 == null) return false;
        if (root2 == null) return true;
        Queue<Node> queue = new LinkedList<>();
        queueErgodic(queue,root1);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            if (cur.val == root2.val){
                if (binaryTreeIsSamePlus(cur,root2)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean isContainPlus(Node root1,Node root2){
        if (root1 == null && root2 == null) return true;
        if (root1 == null) return false;
        if (root2 == null) return true;
        if (root1.val == root2.val){
            if (binaryTreeIsSamePlus(root1,root2)){
                return true;
            }
        }
        return isContain(root1.left,root2) || isContain(root1.right,root2);
    }
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.create();
        BinaryTree binaryTree1 = new BinaryTree();
        binaryTree1.create();
        boolean flog = binaryTree1.isContainPlus(binaryTree.root,binaryTree1.root);
        System.out.println(flog);
    }
}
